The present disclosure relates to processor allocation generally, that is, to the problem of associating tasks with processing units in a computing system. The disclosure relates more particularly to associations made using derived task spaces and multidimensional task spaces.
Networks and other collections of connected processing units can be much more reliable than a single processing unit for a variety of reasons. When a processing unit fails, its tasks can be reassigned to working units, and new tasks can be diverted away from the failed unit. Tasks can often be performed faster by adding processing units and dividing tasks between processing units, which can then execute the tasks at least partially in parallel. Processing units include individual computer CPUs and supporting circuitry and software necessary for executing a task, as well as larger groups of processors such as multiprocessors and clusters.
One traditional method of associating tasks with processing units includes assigning a name or an ordinal number (sometimes referred to as a whole number or integer) to each task. A similar name or ordinal number is assigned to each processing unit. Names may be strings, enumeration values, or other familiar identifiers. Each task is then placed on a list associated with the assigned processing unit by placing its name, number or other identifier on the list. Each processing unit thus has a list of the tasks it needs to perform. When a processing unit is added to the computing system, tasks must be explicitly sent to the new server. If existing tasks are among those sent, their identifiers must be located in the existing server list, deleted, and then reassigned to a new server.
One variation assigns a fractional number (sometimes referred to as a real number) to each task and a range of fractional values to each processing unit. For instance, each task could be assigned a fraction in the interval [0, 1] on the real number line using the familiar Euclidean metric, with each processing unit being assigned a subinterval within that range. A given task is then associated with a given processing unit if the interval allocated to the processing unit contains the fraction assigned to the task.
With either approach, load balancing may be used to spread tasks evenly among servers or other processing units. Load balancing algorithms determine where to assign each task so that the collection of tasks and processing units satisfies some criterion such as finishing as quickly as possible. To achieve high reliability of the network as a whole, tasks assigned to failed servers are rebalanced across operating servers. This may require redistributing the list associated with a failed processing unit among the currently working processing units. Making, maintaining, and redistributing the lists is a relatively expensive operation. Distributed networks must often execute complicated distributed algorithms using imperfect knowledge to approximate optimal bandwidth, and task lists must often be kept in multiple places to facilitate recovery from failures.
A drawback of the approach that assigns fractions in [0, 1] to tasks is that assigning the fractions may require difficult or arbitrary choices, because only a single fraction value is assigned to a given task. All servers that might be eligible to receive the task must likewise be characterized in the same way, namely, according to the single criterion that was used when characterizing the task by assigning it a fraction value.
Thus, it would be an advancement in the art to provide improved ways to associate tasks with server computers and other processing units so that creating and maintaining conventional task lists is unnecessary.
It would also be an advancement to provide improved ways to associate tasks with processing units such that the tasks and the processors may be characterized according to several criteria.
It would be an additional advancement to provide such improvements which extend the capabilities of existing processor allocation mechanisms, and hence can be used in conjunction with existing mechanisms.
Such improvements are disclosed and claimed herein.